LeetCode——下一个排列

NO.31 下一个排列 中等

思路一：一次遍历法 经过观察发现，降序序列没有更大的排序，例如[9,4,3,2,1]、[7,5,4,2,]等等。

1. 从数组nums的最后一个元素开始，逆序遍历寻找第一个非递增元素nums[i]。例如[1,5,4,7,6,5,3,1]，逆序遍历到第一个非递增元素是4。
2. 此时nums[i]元素的右边是一个递减序列，逆序遍历这个递减序列找到大于nums[i]的元素中最小的一个nums[j](此时右边这个序列是有序的，利用这一性质)。例如，上例中4右边的序列中找到5。
3. 交换nums[i]和nums[j]，此时序列变为[1,5,5,7,6,4,3,1]。然而这个序列并不是我们需要的”下一个排列”，将i之后的元素序列翻转后得到[1,5,5,1,3,4,6,7]才是最终结果。

    public void nextPermutation(int[] nums) {
//        逆序找到第一个非递增元素nums[i]
        int i=nums.length-2;
        while (i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
//        如果nums本身不是递减序列，逆序找到nums[i]元素右边的递减序列中第一个大于nums[i]的元素
        if (i>=0){
            int j=nums.length-1;
            while (j>=0&&nums[j]<=nums[i]){
                j--;
            }
//            交换nums[i]和nums[j]
            swap(nums,i,j);
        }
//        最后翻转nums[i]右边的元素序列，得到参数数组nums的下一个更大的排列
        reverse(nums,i+1);
    }
//    从start号索引开始翻转nums数组元素
    public void reverse(int[] nums,int start){
        int i=start,j=nums.length-1;
        while (i<j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
//    交换nums数组的i和j号索引元素
    private void swap(int[] nums, int i, int j) {
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

时间复杂度：O(n)，在最坏的情况下，只需要对整个数组进行两次扫描

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github